// 给定一个二叉树，返回它的 前序 遍历。

//  示例:

// 输入: [1,null,2,3]  
//    1
//     \
//      2
//     /
//    3 

// 输出: [1,2,3]

// ①递归，大家都会，见二叉树概览.html
// 先推入根节点值,再遍历左子树,
// 左子树如果不存在,返回空数组,
// 左子树如果存在,先推入左子树的值,再继续遍历左子树的左子树,
// 紧接着是左子树的右子树,回到外层,检索根节点的右子树,重复中-左-右-的检索过程
// var preorderTraversal = function(root) {
//     if(!root) return [];
//     let result = [];
//     result.push(root.val);
//     result = result.concat(preorderTraversal(root.left));
//     result = result.concat(preorderTraversal(root.right));
//     return result;
// };

// ②迭代
// 每次压栈，然后弹出，输出
var preorderTraversal = function(root) {
    if (!root) {
        return [];
    }
    // 压栈
    var stack = [root];
    var result = [];
    while (stack.length > 0) {
        // 弹出
        var item = stack.pop();
        result.push(item.val);
        item.right && stack.push(item.right);
        item.left && stack.push(item.left);
    }
    return result;
};